A first in, first out memory system (FIFO) is a memory system from which data items are retrieved in the same sequence in which the data items were stored in the memory system. That is, the first data item stored in a FIFO is the first data item that is retrieved from the FIFO.
FIFO's are commonly used as data rate buffers between systems that transfer data at widely different rates. For example, multiple systems which process and transfer data at widely different rates can be interconnected through an interconnect such as a crossbar. A FIFO can be used to buffer data transferred from a fast device to a slow device, for example, from a computer to a printer. The computer can send character data to a FIFO at a relatively high rate. The printer can then read the data from the FIFO at a much slower rate and in the same order that the data was sent by the computer. Similarly, a FIFO can be used to buffer data transferred from a slow device to a fast device, e.g., from a keyboard to a computer. Here, the keyboard can send character data to a FIFO at a relatively low rate. The computer can then read the data from the FIFO at a much higher rate and in the order that the data was sent by the keyboard. Therefore, the computer may perform other tasks while the FIFO is slowly being filled with data and later retrieve the data from the FIFO in order.
A FIFO implemented in hardware, e.g., in an integrated computer, typically includes a finite number of memory positions into which data items can be stored. Each memory position can be, for example, a register. In general, each memory position of the FIFO can store a single data item. Each data item typically has a fixed length, but some FIFOs store data items of variable length.
Many applications require buffering of multiple ordered sets, or multiple sets of data items. In such applications, sequential ordering of data items are generally only important among data items of the same set. One such example is a scheduler that spools task sets for multiple processors. The scheduler can compile an ordered set of packets for each processor and each processor can sequentially execute a task set which includes the ordered set of packets specific to the processor. Therefore, it is important to maintain sequential ordering of packets within each ordered set for each processor. But, it is not necessary to maintain sequential ordering of packets among the plurality of ordered sets.
One method of buffering data entries of multiple ordered sets is to sort the data entries into multiple, separate FIFO's, i.e., one for each ordered set. In some applications, e.g., when multiple FIFO's are implemented in hardware, it is necessary to pre-allocate memory space for such FIFO's and therefore to fix a maximum number of FIFO's and a maximum number of memory positions for each such FIFO. In systems which use multiple FIFO's, the number of FIFO's and the maximum requisite length of each FIFO can be particularly difficult to predict and can depend upon the manner in which such systems are used. Fixing the maximum number of FIFO's too low increases the likelihood that such a system finds insufficient FIFO's to operate properly. Fixing the maximum number of FIFO's too high allocates more memory, and therefor more circuitry, than is necessary for implementation of the multiple FIFO's. In addition, one of a number of FIFO's of fixed length can exhaust available memory positions while other FIFO's have a surplus of memory positions. Accordingly, fixing the number of FIFO's and the number of memory positions for each FIFO can result in a memory position shortage in one FIFO and a simultaneous memory position surplus in other FIFO's.
Some attempts have been made to implement multiple ordered sets in a single FIFO. However, such can result in a problem known as blocking. Blocking refers to the unavailability of data items of one ordered set stored in a FIFO as a result of storage of a data item of another ordered set in a preceding memory in the order of the FIFO. The following example is illustrative. Suppose a scheduler collects packets into respective ordered sets representing respective tasks to be performed by respective processors. Suppose further that the packets are spooled through a single FIFO regardless of the particular processor which is to receive each packet. If packets intended for a first processor follow packets intended for a second processor in the sequence of the single FIFO, the packets intended for the first processor cannot be sent to the first processor until the preceding packets for the second processor are sent. If the second processor is busy and cannot receive the packets from the FIFO, the packets intended for the first processor are blocked. Even if the first processor is ready to receive packets from the FIFO, the packets are blocked pending receipt of the preceding packets by the second processor. Accordingly, the first processor is idle and wasted as long as the second processor is busy. Thus, blocking leads to unnecessarily wasted resources and time.
What is needed is a method and apparatus for buffering data entries of multiple ordered sets without a need to allocate an excess of FIFO's or slots per FIFO and in a manner such that blocking of an oldest data entry which is a member of one set does not cause excessive delay in release of oldest data entries of other sets from the FIFO.